package com.demo.algorithms.sort;


import java.util.Arrays;
import java.util.Random;

/**
 * 冒泡排序
 * 它重复地走访过要排序的元素列，依次比较两个相邻的元素，
 * 如果顺序（如从大到小、首字母从Z到A）错误就把他们交换过来。
 * 走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素列已经排序完成。
 * <p>
 * 总结：
 * 1.进行数组的大小 - 1次循环
 * 2.每一次循环排序的次数逐渐减少
 * 3.如果发现某次循环排序没有发现一次交换，则可以提前结束排序（优化）
 *
 * @author: 蔡奇峰
 * @date: 2020/7/17 22:09
 **/
public class BubbleSort {

    public static void main(String[] args) {
//        int[] arr = {6, 2, 5, 2, 8, 66, 22, 17, 18, 1, 88, 98, 168, 178};

        int[] arr = new int[7780];
        for (int i = 0; i < 7780; i++) {

            arr[i] = new Random().nextInt(1800);
        }
        System.out.println("数组排序前：" + Arrays.toString(arr));

        long timeMillis = System.currentTimeMillis();
        sort(arr);
        long timeMilli = System.currentTimeMillis();

        System.out.println("数组排序后：" + Arrays.toString(arr));
        System.out.println("冒泡排序耗时：" + (timeMilli - timeMillis));


        /*System.out.print("数组排序后：");
        for (int k = 0; k < num.length; k++) {
            System.out.printf("%d\t", num[k]);
        }*/
    }


    /**
     * 已经优化的冒泡排序（从小到大排序）
     *
     * @param array 需要排序的数组
     */
    public static void sort(int[] array) {
        // 临时变量,用于辅助交换
        int temp;

        // 交换标识，默认没有发生交换
        boolean flag = false;
        // 两两比较，因此最后一个是倒数第二个（length - 1)
        for (int i = 0; i < array.length - 1; i++) {

            // length - 1 - i：比较次数逐渐减少，每循环一次 - 1,即 - i
            // 后面的即为最大的因此不需要再排序
            for (int j = 0; j < array.length - 1 - i; j++) {
                // 比较大小，大于则进行交换
                if (array[j] > array[j + 1]) {
                    temp = array[j];
                    // 发生交换
                    flag = true;

                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                }
            }
            // 如果没有发生交换，说明已经排好了，则结束循环
            if (!flag) {
                break;
            }
        }

    }
}
